//
// Created by francklinson on 2021/5/24.
//
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int maximumPopulation(vector<vector<int>> &logs) {
        unordered_map<int, int> fre;
        for (auto &x:logs) {
            for (int i = x[0]; i < x[1]; ++i) {
                ++fre[i];
            }
        }
        int maxNum = 0, ansYear = 0;
        for (auto &x:fre) {
            if (x.second > maxNum) {
                maxNum = x.second;
                ansYear = x.first;
            } else if (x.second == maxNum and x.first < ansYear) {
                ansYear = x.first;
            }
        }
        return ansYear;
    }
};

class Solution2 { // 差分法
private:
    static constexpr int offset = 1950;   // 起始年份与起始下标之差

public:
    int maximumPopulation(vector<vector<int>> &logs) {
        vector<int> delta(101, 0);   // 变化量
        for (auto &&log: logs) {
            ++delta[log[0] - offset];
            --delta[log[1] - offset];
        }
        int mx = 0;   // 人口数量最大值
        int res = 0;   // 最大值对应的最小下标
        int curr = 0;   // 每一年的人口数量
        // 前缀和
        for (int i = 0; i < 101; ++i) {
            curr += delta[i];
            if (curr > mx) {
                mx = curr;
                res = i;
            }
        }
        return res + offset;   // 转回对应的年份
    }
};


int main() {
    vector<vector<int>> logs{{1993, 1999},
                             {2000, 2010}};
    Solution2 sol;
    cout << sol.maximumPopulation(logs) << endl;
    return 0;
}